
/*class Solution {
力扣泡泡龙
    //1.被击破的节点泡泡 至多 只有一个子节点泡泡。
    //2.当被击破的节点泡泡有子节点泡泡时，则子节点泡泡将取代被击破泡泡的位置。
    //基本思路：
    //1.通过二叉树的层序遍历求出每层原始的层和
    //2.在层序遍历的时候也可以统计那些只有一个子节点的节点，这些节点都是我们可以去击破的节点。把他用一个队列存储起来
    //3.那些记录下来的可以戳破的节点，就成为了可以去尝试的优化方案。但是他们在每一层的表现和影响不同。例如示例2中
    //击破的6，在第二层是6，在第三层的表现就是4，第4层的表现就是3,5.这些表现需要随着层序遍历不断地下层。
    //4.层序遍历在下层的过程中，也会加入新的优化方案，这些方案和3里面的一样都被levelUpGroups记录下来。
    //5.完成一层的层序遍历后，我们可以获取到一层的原始层和。然后遍历levelUpGroups这个优化方案，最终算出该层的最大可能性。
    //6.完成所有层的遍历，最终就是结果。
    //性能方面需要注意的是:当一个优化方案和该层级的元素数量一样的时候，说明他的方案是取消整层。这样的优化方案是没有意义的。
    //比如最后一层是-2,-5。我把他全拿掉，那么就这层就成了0.但是其实本质是一出一层，这一层就不该再被计算。
    int rowSum = 0;
    public int getMaxLayerSum(TreeNode root) {
        int max = root.val;
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Queue<TreeNode>> levelUpGroups = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int rowSize = q.size();
            rowSum = 0;
            for(int i = 0; i < rowSize ; i ++){
                TreeNode node = q.remove();
                //被击破的泡泡至多之后一个子节点
                if(null == node.left || null == node.right){
                    Queue<TreeNode> group = new LinkedList<>();
                    group.add(node);
                    levelUpGroups.add(group);
                }
                if(null != node.left)
                    q.add(node.left);
                if(null != node.right)
                    q.add(node.right);
                rowSum += node.val;
            }
            max = Math.max(max,rowSum);
            //计算当层点击泡泡后的各种方案的最大值
            //一个group中即便有个多个值，也表达的着是这多个值同时被移除的机会，因为有些机会是上层击破带来的。
            //levelUpGroups是动态的(遍历的时候也在删除)要注意这点

            int levelUpGroupsSize = levelUpGroups.size();
            for(int i = 0; i < levelUpGroupsSize; i++){
                Queue<TreeNode> group = levelUpGroups.remove();
                int diff = 0;
                int groupSize = group.size();
                for(int j = 0; j < groupSize; j++){
                    TreeNode pop2Click = group.remove();
                    diff -= pop2Click.val;

                    if(null != pop2Click.left){
                        group.add(pop2Click.left);
                        diff += pop2Click.left.val;
                    }

                    if(null != pop2Click.right){
                        group.add(pop2Click.right);
                        diff += pop2Click.right.val;
                    }
                }

                //这句是性能测试能过的关键
                //首先要明白一层中的元素数量rowSize是不可能有比他更大的值
                //那么一个优化方案中的元素个数都和这个层里面的元素个数相等了，那么必然表示这个优化方案要提升整层
                //而提升整层是毫无意义的事情。
                if(rowSize != groupSize && 0 != group.size()){
                    levelUpGroups.add(group);
                }
                if(0 - diff != rowSum)
                    max = Math.max(max,rowSum + diff);
            }
        }
        return max;
    }
}*/
